\documentclass[acmtalg]{acmsmall}
%\documentclass[11pt]{article}


\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xspace}
\usepackage{tikz}
\usetikzlibrary{backgrounds,positioning,fit,patterns,shadows,calc}

%\usepackage[numbers,sort]{natbib}

\bibliographystyle{splncs03}
%\bibliographystyle{alpha}


\newcommand*\samethanks[1][\value{footnote}]{\footnotemark[#1]}
\renewcommand{\paragraph}[1]{\medskip\noindent{\bf #1.}\xspace}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: Reduce margine
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage[left=1in,top=1in,right=1in,bottom=1in]{geometry} % Does NOT work right now
%\usepackage{fullpage}
%\usepackage{times}
\usepackage{booktabs}
\usepackage{threeparttable}
%\usepackage[small,compact]{titlesec}

%\setlength{\textheight}{9.2in}
%\setlength{\textwidth}{6.55in}


%http://tex.stackexchange.com/questions/4891/how-do-i-control-the-spacing-above-a-new-paragraph

%\makeatletter
%\renewcommand{\paragraph}{%
%  \@startsection{paragraph}{4}%
%  {\z@}{1ex \@plus 1ex \@minus .2ex}{-1em}%
%  {\normalfont\normalsize\bfseries}%
%}
%\makeatother

%**************************************************
%**************************************************
%**************************************************


%--------------------------------------------------------------
%--------------------------------------------------------------
% Packages
%--------------------------------------------------------------
%--------------------------------------------------------------

\usepackage{tikz}
\usetikzlibrary{backgrounds,positioning,fit,patterns,shadows,calc}

\usepackage{epsfig}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{amsmath}



\usepackage{calligra}
\usepackage[T1]{fontenc}

% ---------------------------------------------------------------------------------------
% ----- from http://mirrors.ibiblio.org/CTAN/macros/latex/exptl/thmtools/thmtools.pdf
%\usepackage{amsthm}
%\usepackage{thmtools}


\usepackage{paralist}

%\usepackage{
%nameref,%\nameref
%hyperref,%\autoref
%% n.b. \Autoref is defined by thmtools
%cleveref,% \cref
%% n.b. cleveref after! hyperref
%}
%
%\usepackage{nameref}
% Nicer hyperref obtained from Babis
\usepackage{colordvi}
\usepackage{color}
\definecolor{ForestGreen}{rgb}{0.1333,0.5451,0.1333}
\definecolor{DarkRed}{rgb}{0.8,0,0}
\definecolor{Red}{rgb}{1,0,0}
\usepackage[linktocpage=true,
%	pagebackref=true,
	colorlinks,
	linkcolor=DarkRed,citecolor=ForestGreen,
	bookmarks,bookmarksopen,bookmarksnumbered]
	{hyperref}
%Older style
%\usepackage[linktocpage=true]{hyperref}

\makeatletter \let\cl@chapter\relax \makeatother

\usepackage{cleveref}

%\usepackage{thm-restate} % See section 1.4 of the pdf above

% ---------------------------------------------------------------------------------------


\usepackage{xspace}
%\usepackage{theorem}
%\usepackage{graphicx}
%\usepackage{graphics}
%\usepackage{colordvi}
\usepackage{color}
%\usepackage{psfrag}
%\usepackage{eepic}
%\usepackage{subfigure}
%\usepackage[section]{algorithm}
%\usepackage{algorithmicx}
%\usepackage{algpseudocode}
%\usepackage[noend]{algpseudocode}
%\usepackage{wrapfig}
%\usepackage{lipsum}
\usepackage{enumitem}
\usepackage{comment}
%\usepackage{caption3} %reduce the size of captions under tables and figures. `caption3' works for sigalternate
\usepackage{caption}
\usepackage{subcaption}
\usepackage[noend]{algorithmic}
\usepackage[section,boxed]{algorithm}
%\usepackage{algorithmicext}


%---------------------------------
% Definitions
%---------------------------------

\def\cP{\mathcal{P}}
\def\cH{\mathcal{H}}
\def\cA{\mathcal{A}}
\def\cT{\mathcal{T}}
\def\cD{\mathcal{D}}
\def\cC{\mathcal{C}}
\def\cG{\mathcal{G}}
\def\cJ{\mathcal{J}}
\def\cF{\mathcal{F}}
\def\cX{\mathcal{X}}
\def\cY{\mathcal{Y}}

\newcommand{\eps}{\varepsilon}
\renewcommand{\varepsilon}{\epsilon}
\newcommand{\st}{{\sf ST}\xspace}
\newcommand{\mcds}{{\sf MCDS}\xspace}
\newcommand{\scs}{{\sf SCS}\xspace}
\newcommand{\mis}{{\sf MIS}\xspace}
\newcommand{\mds}{{\sf MDS}\xspace}
\newcommand{\mhs}{{\sf MHS}\xspace}
\newcommand{\rmds}{{\sf RMDS}\xspace}
\newcommand{\mcsc}{{\sf MCSC}\xspace}
\newcommand{\bmds}{{\sf BMDS}\xspace}

\newcommand{\dimension}{\textsc{dim}}

%\newconstruct{\PROC}{\textbf{procedure}}{}{\ENDPROC}{\textbf{end on}}

%\def\polylog{{\mathop{\mathrm{polylog}}\nolimits}}

\def\polylog{\operatorname{polylog}}

\newboolean{short}
\setboolean{short}{false}

\newcommand{\shortOnly}[1]{\ifthenelse{\boolean{short}}{#1}{}}
\newcommand{\onlyShort}[1]{\ifthenelse{\boolean{short}}{#1}{}}
\newcommand{\longOnly}[1]{\ifthenelse{\boolean{short}}{}{#1}}
\newcommand{\onlyLong}[1]{\ifthenelse{\boolean{short}}{}{#1}}




%--------------------------------------------------------------
%--------------------------------------------------------------
%Theorems and such
%--------------------------------------------------------------
%--------------------------------------------------------------

%---- The code below is needed to make many refname commands work ----
%---- See http://tex.stackexchange.com/questions/49937/a-problem-with-thmtools-and-cleveref ----

%\makeatletter
%\def\thmt@refnamewithcomma #1#2#3,#4,#5\@nil{%
%  \@xa\def\csname\thmt@envname #1utorefname\endcsname{#3}%
%  \ifcsname #2refname\endcsname
%%    \csname #2refname\expandafter\endcsname\expandafter{\thmt@envname}{#3}{#4}%
%  \fi
%}
%\makeatother
%
\newtheorem{observation}{Observation}{\bfseries}{\itshape}
\newtheorem{claim}{Claim}{\bfseries}{\itshape}


%\usepackage{thm-llncs}

%\declaretheorem[numberwithin=section,refname={Theorem,Theorems},Refname={Theorem,Theorems}]{theorem}
%\declaretheorem[numberwithin=section]{theorem}
%\declaretheorem[numberlike=theorem,refname={Lemma,Lemmas},Refname={Lemma,Lemmas}]{lemma}
%\declaretheorem[numberlike=theorem,refname={Corollary,Corollaries},Refname={Corollary,Corollaries}]{corollary}
%\declaretheorem[numberlike=theorem,name={Corollary},refname={Corollary,Corollaries},Refname={Corollary,Corollaries}]{corr}
%\declaretheorem[numberlike=theorem,refname={Proposition,Propositions},Refname={Proposition,Propositions}]{proposition}
%\declaretheorem[numberlike=theorem,refname={Observation,Observations},Refname={Observation,Observations}]{observation}
%\declaretheorem[numberlike=theorem,refname={Assumption,Assumptions},Refname={Assumption,Assumptions}]{assumption}
%\declaretheorem[numberlike=theorem,refname={Claim,Claims},Refname={Claim,Claims}]{claim}
%\declaretheorem[numberlike=theorem,refname={Definition,Definitions},Refname={Definition,Definitions}]{definition}
%\declaretheorem[style=remark,numberwithin=section,refname={Remarks,Remarks},Refname={Remarks,Remarks}]{remark}


%
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{definition}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{observation}[theorem]{Observation}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{claim}[theorem]{Claim}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{definition}[theorem]{Definition}
%
%
%%\newenvironment{exercise}{\underline{\bf Exercise}: }{}
%%%\newenvironment{proof}{\par \smallskip{\bf Proof:}}{\hfill\stopproof}
%%\def\stopproof{\square}
%%\def\square{\vbox{\hrule height.2pt\hbox{\vrule width.2pt height5pt \kern5pt
%%\vrule width.2pt} \hrule height.2pt}}
%%
%%%\newenvironment{definition}{\underline{\bf Definition}: }{}
%%%\newtheorem{definition}[theorem]{Definition}
%%\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
%%%\newenvironment{definition}[1][Definition]{\begin{trivlist}
%%%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%


%-------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------
% Comments
%-------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------

%\addtolength{\voffset}{-0.15in}


%\def\ShowComment{True}

\ifdefined\ShowComment

\def\danupon#1{\marginpar{$\leftarrow$\fbox{D}}\footnote{$\Rightarrow$~{\sf #1 --Danupon}}}
\def\hsinhao#1{\marginpar{$\leftarrow$\fbox{H}}\footnote{$\Rightarrow$~{\sf #1 --Hsin-Hao}}}

\else

\def\danupon#1{}
\def\hsinhao#1{}

\fi



% This part changed {\em xxx} in the italic evironment (e.g. in theorem statements) to other fonts
% such as \sffamily,\bfseries, etc.
% See: http://tex.stackexchange.com/questions/6754/what-is-the-canonical-way-to-redefine-the-emph-command
% and http://www.forkosh.com/pstex/latexcommands.htm

%\makeatletter
%\DeclareRobustCommand{\em}{%
%  \@nomath\em \if b\expandafter\@car\f@series\@nil
%  \bfseries \else \itshape \fi}
%\makeatother




%--------------------------------------------------------------
%--------------------------------------------------------------
% Title page stuff
%--------------------------------------------------------------
%--------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver for title page
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usepackage{titling}
%\setlength{\droptitle}{-55pt}


\markboth{}{}
\title{Distributed Symmetry Breaking in Hypergraphs}

%\titlerunning{Distributed Symmetry Breaking in Hypergraphs}

\author{
Shay Kutten\affil{Faculty of IE\&M, Technion, Haifa, Israel}%\inst{1}\fnmsep\thanks{Research supported in part by the Israel Science Foundation and by the Technion TASP center.}
Danupon Nanongkai\affil{KTH Royal Institute of Technology, Stockholm, Sweden}%\inst{2}\fnmsep\thanks{This work was partially done while at ICERM, Brown University USA and Nanyang Technological University, Singapore.}
Gopal Pandurangan\affil{Department of Computer Science, University of Houston, USA}%\inst{3}\fnmsep\thanks{This work was done while at Nanyang Technological University and Brown University. Research supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, Singapore MOE  AcRF Tier 1 grant MOE2012-T1-001-094, and a grant from the US-Israel Binational Science Foundation (BSF).}
Peter~Robinson\affil{Queen's University Belfast} %\inst{4} %\thanks{Research supported by the grant Fault-tolerant Communication Complexity in Wireless Networks from the Singapore MoE AcRF-2.}
}


%\institute{Shay Kutten \at Faculty of IE\&M, Technion, Haifa, Israel \and Danupon Nanongkai \at Faculty of Computer Science, University of Vienna, Austria \and Gopal Pandurangan \at Department of Computer Science, University of Houston, USA \and Peter Robinson \at Queen's University Belfast}


\begin{document}



\input{abstract}
\begin{bottomstuff}
A preliminary version of this paper appeared in the proceedings of the {\em 28th International Symposium on Distributed Computing (DISC)}, Austin, TX, USA, 469-483. \\
Shay Kutten was supported in part by the Israel Science Foundation and by the Technion TASP center.  
Danupon Nanongkai was partially at ICERM, Brown University USA and Nanyang Technological University, Singapore.
Gopal Pandurangan was at Nanyang Technological University and Brown University and was supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, Singapore MOE  AcRF Tier 1 grant MOE2012-T1-001-094, and  US-Israel Binational Science Foundation (BSF) grant 2008348.
Peter Robinson was at the National University of Singapore and was supported in part by the grant Fault-tolerant Communication Complexity in Wireless Networks from the Singapore MoE AcRF-2.
\end{bottomstuff}
\category{C.2.4}{Computer Systems Organization}{Computer-Communication Networks}[Distributed Systems]
\category{F.2.2}{Theory of Computation}{Analysis of Algorithms and Problem Complexity}[Nonnumerical Algorithms and Problems]
%\category{F.0}{Theory of Computation}{General}
\category{G.2.2}{Mathematics of Computing}{Discrete Mathematics}[Graph Theory]

\terms{Theory, Algorithms}
\keywords{hypergraph; symmetry breaking; lower bound; distributed algorithm}

\acmformat{Kutten, S., Nanongkai, D., Pandurangan, G., Robinson, P. 2015. Distributed Symmetry Breaking in Hypergraphs.}

\maketitle


%\newpage
%\pagenumbering{arabic}
\tikzstyle{v}=[circle,draw=black,fill=white!30,thick,inner sep=2pt,minimum size=7mm,circular drop shadow]
\tikzstyle{b}=[v,double]


\input{intro}
\input{prelim}
\input{algorithms}
\input{conclusion}
%\paragraph*{\bf Conclusion.}


\onlyShort{\vspace{-0.2in}} 
\bibliography{papers}


\end{document}
